package com.leet.code.lcof;

import java.util.HashSet;
import java.util.LinkedList;

public class Code38 {

    public static void main(String[] args) {
        Code38 code38 = new Code38();
        for (String s : code38.permutation("aab")) {
            System.out.println(s);
        }

    }

    LinkedList<Character> list = new LinkedList<>();
    HashSet<String> hs = new HashSet<>();

    public String[] permutation(String s) {
        for (int i = 0; i < s.length(); i++) {
            list.add(s.charAt(i));
        }
        dfs(new char[s.length()], 0);
        String[] sr = new String[hs.size()];
        return hs.toArray(sr);
    }


    public void dfs(char[] chars, int start) {
        if (start == chars.length) {
            hs.add(new String(chars));
            return;
        }

        int s = list.size();
        for (int i = 0; i < s; i++) {
            chars[start] = list.removeFirst();
            dfs(chars, start + 1);
            list.add(chars[start]);
        }

    }


}
